当前位置:网站首页>C language - stack
C language - stack
2022-07-04 10:24:00 【sqjddb】
Definition of stack
Stack (stack) Also known as the stack , It's a limitation Insert and delete only at the end of the table Operation of the The linear table
This end is called To the top of the stack , The other end is called At the bottom of the stack . The data elements in the stack comply with Last in, first out Principles .
To a stack Insert The new element is also called Into the stack 、 Push or push , Make it the new top element
From a stack Delete Elements are also called Out of stack or out of stack .
C Language implementation stack
analysis :
You can use arrays or linked lists to achieve , But the cost of inserting data into the tail of the array is relatively small . The complete procedure is as follows :
The header file
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
typedef int STDatatype;
typedef struct Stack
{
STDatatype* p;
int top;
int capacity;
}ST;
// Initialization stack
void StackInit(ST* ps);
// Free up stack space
void StackDestroy(ST* ps);
// Element stack
void StackPush(ST* ps, STDatatype x);
// Out of the stack
void StackPop(ST* ps);
// Sentenced to empty
bool StackEmpty(ST* ps);
// Calculate the number of elements in the stack
int StackSize(ST* ps);
// Back to top of stack element
STDatatype StackTop(ST* ps);
Function implementation file
#include "Stack.h"
void StackInit(ST* ps)
{
assert(ps);
ps->p = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
if (ps->p)// If p by NULL, Can not be free
{
free(ps->p);
}
ps->p= NULL; //free After the empty , Avoid wild pointer problems
ps->top = 0;
ps->capacity = 0;
}
void StackPush(ST* ps, STDatatype x)
{
assert(ps);
// Check if there's enough space , Not enough capacity
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDatatype* tmp = realloc(ps->p, sizeof(STDatatype)*newcapacity);
ps->p= tmp;
ps->capacity = newcapacity;
}
ps->p[ps->top] = x;
ps->top++;
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;//-> Priority over --
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
STDatatype StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->p[ps->top - 1];
}
Main function test file
#include "Stack.h"
int main()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
printf("%d ", StackTop(&st));
StackPop(&st);
printf("%d ", StackTop(&st));
StackPop(&st);
StackPush(&st, 4);
StackPush(&st, 5);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestroy(&st);
return 0;
}
Running results
Classical bracket matching problem
Ideas
Traversal string , If the current character is an open parenthesis , Push , Wait for the right parenthesis to determine whether it matches , If it's right bracket , Match the character at the top of the stack with the current character , Stack top element out of stack , Make the character at the top of the stack become an earlier left parenthesis , It is convenient to match with the more backward right parenthesis . Specific ideas and details are shown in the following program notes
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
// First, implement a stack
typedef int STDatatype;
typedef struct Stack
{
STDatatype* p;
int top;
int capacity;
}ST;
void StackPush(ST* ps, STDatatype x)
{
assert(ps);
// Check if there's enough space , Not enough capacity
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDatatype* tmp = realloc(ps->p, sizeof(STDatatype)*newcapacity);
ps->p = tmp;
ps->capacity = newcapacity;
}
ps->p[ps->top] = x;
ps->top++;
}
void StackInit(ST* ps)
{
assert(ps);
ps->p = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
assert(ps);
if (ps->p)// If p by NULL, Can not be free
{
free(ps->p);
}
ps->p = NULL; //free After the empty , Avoid wild pointer problems
ps->top = 0;
ps->capacity = 0;
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;//-> Priority over --
}
STDatatype StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->p[ps->top - 1];
}
bool isValid(char * s){
ST st;
StackInit(&st);
bool matchflag = true;
while (*s)
{
if (*s == '{' || *s == '[' || *s == '(')
{
StackPush(&st, *s);// If it's left parenthesis , Push
s++;
}
else
{
// The program comes to this , The current character is the right bracket
// If there are no elements in the stack , Indicates that there is no left parenthesis matching the current right parenthesis
if (StackEmpty(&st))
{
matchflag = false;
break;
}
// If there are elements in the stack , Take it out to match the current right parenthesis
char ch = StackTop(&st);
// The matched left parenthesis should be out of the stack
StackPop(&st);
// See if it matches
if (
(*s == '}'&&ch != '{') ||
(*s == ']'&&ch != '[') ||
(*s == ')'&&ch != '(')
)
{
matchflag = false;
break;
}
else
{
s++;// If the match , Continue traversing backwards
// See whether the following right parenthesis matches the element at the top of the stack
// It makes perfect use of the characteristics of stack first in and last out
}
}
}
if (matchflag == true)
{
matchflag = StackEmpty(&st);
// If the characters are traversed and the stack is not empty , It shows that the left parenthesis in the stack is lonely , Mismatch
}
StackDestroy(&st);
return matchflag;
}
int main()
{
// Test several examples
char *p0 = "{[]}";
printf("%d\n", isValid(p0));
char *p1= "()";
printf("%d\n", isValid(p1));
char *p2 = "()[]{}";
printf("%d\n", isValid(p2));
char *p3 = "(]";
printf("%d\n", isValid(p3));
char *p4 = "([)]";
printf("%d\n", isValid(p4));
}
Running results :
边栏推荐
- View CSDN personal resource download details
- The time difference between the past time and the present time of uniapp processing, such as just, a few minutes ago, a few hours ago, a few months ago
- Rhsca day 11 operation
- Rhcsa - day 13
- OSPF comprehensive experiment
- PHP代码审计3—系统重装漏洞
- 对于程序员来说,伤害力度最大的话。。。
- 六月份阶段性大总结之Doris/Clickhouse/Hudi一网打尽
- Exercise 7-4 find out the elements that are not common to two arrays (20 points)
- Rhcsa12
猜你喜欢
转载:等比数列的求和公式,及其推导过程
Devop basic command
OSPF comprehensive experiment
Custom type: structure, enumeration, union
Some summaries of the third anniversary of joining Ping An in China
leetcode1-3
5g/4g wireless networking scheme for brand chain stores
When I forget how to write SQL, I
六月份阶段性大总结之Doris/Clickhouse/Hudi一网打尽
Servlet基本原理与常见API方法的应用
随机推荐
入职中国平安三周年的一些总结
The future education examination system cannot answer questions, and there is no response after clicking on the options, and the answers will not be recorded
For programmers, if it hurts the most...
How can Huawei online match improve the success rate of player matching
Uniapp--- initial use of websocket (long link implementation)
Realsense d435 d435i d415 depth camera obtains RGB map, left and right infrared camera map, depth map and IMU data under ROS
Exercise 9-5 address book sorting (20 points)
Exercise 7-8 converting strings to decimal integers (15 points)
Go context basic introduction
Tables in the thesis of latex learning
Hands on deep learning (37) -- cyclic neural network
Use C to extract all text in PDF files (support.Net core)
How to teach yourself to learn programming
uniapp---初步使用websocket(长链接实现)
Vs201 solution to failure to open source file HPP (or link library file)
DML statement of MySQL Foundation
Hands on deep learning (46) -- attention mechanism
Servlet基本原理与常见API方法的应用
Exercise 9-4 finding books (20 points)
BGP advanced experiment