栈的实现及基本操作c++
时间: 2023-10-11 13:13:27 浏览: 87
栈是一种先进后出的数据结构,可以用数组或链表来实现。以下是使用数组实现栈的基本操作:
1. 创建栈:定义一个数组和一个指向栈顶元素的指针top,初始值为-1。
```
#define MAXSIZE 100
typedef struct{
int data[MAXSIZE];
int top;
}Stack;
Stack* createStack(){
Stack* s = (Stack*)malloc(sizeof(Stack));
s->top = -1;
return s;
}
```
2. 判断栈是否为空:如果栈顶指针为-1,则栈为空。
```
int isEmpty(Stack* s){
return s->top == -1;
}
```
3. 判断栈是否已满:如果栈顶指针等于MAXSIZE-1,则栈已满。
```
int isFull(Stack* s){
return s->top == MAXSIZE-1;
}
```
4. 入栈:将元素插入到栈顶,同时将栈顶指针加1。
```
void push(Stack* s, int x){
if(isFull(s)){
printf("Stack is full.\n");
return;
}
s->data[++s->top] = x;
}
```
5. 出栈:将栈顶元素弹出,同时将栈顶指针减1。
```
int pop(Stack* s){
if(isEmpty(s)){
printf("Stack is empty.\n");
return -1;
}
return s->data[s->top--];
}
```
6. 取栈顶元素:返回栈顶元素的值,但不弹出。
```
int top(Stack* s){
if(isEmpty(s)){
printf("Stack is empty.\n");
return -1;
}
return s->data[s->top];
}
```
7. 清空栈:将栈顶指针设为-1。
```
void clearStack(Stack* s){
s->top = -1;
}
```
例如,使用上述栈操作可以实现一个简单的括号匹配程序:
```
int match(char left, char right){
return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}
int isValid(char* s){
Stack* stack = createStack();
int i = 0;
while(s[i]){
if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
push(stack, s[i]);
}
else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){
if(isEmpty(stack) || !match(pop(stack), s[i])){
return 0;
}
}
i++;
}
return isEmpty(stack);
}
```