栈是什么?
栈是一种结构,也是一种方式。
栈代表着“后进先出”,我是这么理解的(如图)
就像是放在试管里的鸡蛋,新放进去的鸡蛋肯定是在最上层,想拿走的话只能从最上层一个个拿,这种方式叫做栈。
以下是百度百科的解释,用以对比。
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
接下来看题目中,栈的定义
typedef int ElemType;struct StackRecord;typedef struct StackRecord *Stack;struct StackRecord{ int Capacity; //栈容量 int Top; //栈顶,初始为-1。 ElemType *Array;};
栈顶初始为-1,有第一个元素时直接++就行了,Top=0,此时Capacity=1.
2488 括号匹配可以百度搜索,是一道很经典的题,具体解法和思路都有的
2489 后缀表达式求值 和树的内容有关,可以等学了树以后再来做这题
这题实现是很简单,但是要确切明白原理不容易(不写是因为我也不是很懂_(:з」∠)_),步骤如下:
1:if(输入是数字) 则存入栈中
else(是运算符) 取出栈顶两个元素,按运算符计算,将结果存入栈中
2:重复1的步骤,直至输入停止
注意此方法只适用于 确保输入合法 的情况
2277 栈的创建
Stack CreateStack(int MaxElements){ Stack s = (StackRecord *)malloc(sizeof(StackRecord)); s->Top = -1; s->Capacity = MaxElements; s->Array=(int *)malloc(sizeof(int)*s->Capacity); return s;}2280 元素进栈
做的时候很容易 直接把Top拿来当常量用 ,注意应该是 S->Top 。
void Push(Stack S, ElemType x){ if (S->Top + 1 == S->Capacity) return; S->Top++; S->Array[S->Top] = x;}
队比栈更符合正常思维,所以更好理解。
队就像排队,进来只能放在队尾,出去只能从队首出去,那么队中间的呢?就慢慢等咯
做了链表、栈再做队就会觉得比较轻松
队列置空时注意把所有参数都回到初始值。
//2249
void MakeEmpty(Queue Q){ int i = Q->Front; for (; i <= Q->Rear; i++) Q->Array[i] = 0; Q->Size = 0; Q->Front = 0; Q->Rear = -1;}//2294 队列创建时,先给队结构L申请空间,再按照给定的最大容量申请 array数组的空间
Queue CreateQueue(int MaxElements){ Queue L = (Queue)malloc(sizeof(QueueRecord)); L->Capacity = MaxElements; L->Array = (ElemType *)malloc(sizeof(ElemType)*L->Capacity); L->Front = 0; L->Rear = -1; L->Size = 0; return L;}
2298 元素入队
void Enqueue(Queue Q, ElemType X){ if (Q->Capacity == Q->Size) return; Q->Rear++; Q->Array[Q->Rear] = X; Q->Size++;}