C语言数据结构与算法 | 第二集

2025年3月17日 | 阅读11分钟

栈和队列

本教程将介绍C语言中另外两种线性数据结构——栈和队列。在本教程的第一部分，我们回顾了数组、动态数组和链表的概念。栈和队列都是**用户定义**的，这意味着当我们说int arr[]时，编译器能识别它是一个数组，但当我们说Stack时，编译器在程序中没有定义它就无法识别。

栈

栈是一种线性数据结构。它基于**“后进先出”（LIFO）**的原理实现。这意味着最后插入栈的元素将是第一个被删除的元素。栈**只有一个开口**，这意味着要插入或删除元素，我们需要使用同一个末端。当我们向栈中插入元素时，**我们将元素堆叠起来**——新元素放在现有元素之上。插入所有元素后，如果我们想从栈中删除元素，最后插入的元素将是第一个被取出的。

术语

向栈中插入元素：**push**
从栈中删除元素：**pop**
栈的末端/开口：**栈顶**

栈的函数

push(element)	将指定元素插入栈中
pop()	删除并返回栈顶元素
top()	返回栈顶元素
peek()	与top()相同
size()	返回指定栈的大小
empty()	检查给定栈是否为空

Push和Pop

Push和pop是栈的两个主要操作。因此，让我们详细了解它们

假设我们有一个名为“Hundreds”的栈。

它的容量是 10*sizeof(integer) = 40 字节。

Top索引 = 3，

栈顶元素 = 400

Data Structures and Algorithms in C|Set-2

它有四个元素。现在让我们对其进行push和pop操作

push(Hundreds, 550)

检查栈是否已满。如果已满，则无法执行push操作。总容量 = 40 字节。已用容量 = 16 字节。因此，栈未满。
top = top + 1;
Hundreds[top] = 550
Hundreds[4] = 550。

pop()

550不是100的倍数。我们错误地将其推入了栈。它在栈顶。现在，我们需要将其弹出。

1. 检查栈是否为空。如果为空，则无法执行pop操作。

如果 top_index = -1

栈为空

但这里，top_index = 4。因此栈不为空。

2. top = top - 1

Hundreds[top]

现实生活中的栈的例子

香槟塔
摆好所有杯子后，你无法从塔的底部取走杯子。它会使整个塔倒塌。因此，最后摆放的杯子——顶部的杯子——应该是第一个被取出的——**LIFO 原理**。
盘子
在厨房堆叠盘子后，我们不会取走最后一个盘子；我们会从顶部取。

栈的实现

在C语言中，我们可以用两种方式实现栈

使用数组
使用链表

1. 使用数组

#include<stdio.h>
#include<stdlib.h>
struct stack
{
	int size;
	int top;
	int *array;
};
struct stack* creation(int size)
{
	struct stack* s = (struct stack*)malloc(sizeof(struct stack));
	s -> top = -1;
	s -> size = size;
	s -> array = (int*)malloc(sizeof(int)*size);
	return s;
}
void display(struct stack* s)
{
	int i;
	if(isEmpty(s))
	{
		printf("The stack is empty\n");
	}
	else
	{
		printf("Elements in the stack: \n");
		for(i = s->top; i >= 0; i--)
		{
			printf("%d\n", s->array[i]);
		}
	}
}
int isEmpty(struct stack* s)
{
	int Empty = (s->top == -1);
	
	return Empty;
}
int isFull(struct stack* s)
{
	int Full = (s->top == s->size-1);
	return Full;
}
void push(struct stack* s, int element)
{
	if(isFull(s))
	{
		return;
	}
	int index = ++s->top;
	s->array[index] = element;
	printf("\n%d pushed into the stack\n", element);
	display(s);
}
int pop(struct stack* s)
{
	if(isEmpty(s))
	{
		return INT_MIN;
	}
	int index = s->top--;
	return s->array[index];
}
int peek(struct stack* s)
{
	if(isEmpty(s))
	{
		return INT_MIN;
	}
	int index = s->top;
	return s->array[index];
}
void main()
{
	struct stack* s = creation(50);
	push(s, 100);
	push(s, 200);
	push(s, 300);
	pop(s);
	printf("\nAfter pop operation, elements in the stack: \n");
	display(s);
}

输出

100 pushed into the Stack
Elements in the Stack:
100

200 pushed into the Stack
Elements in the Stack:
200
100

300 pushed into the Stack
Elements in the Stack:
300
200
100

After the pop operation, elements in the Stack:
Elements in the Stack:
200
100

就像实现链表一样，我们使用一个结构体来表示栈。在结构体内部，我们创建了一个数组。size和top是栈的属性。

2. 使用链表

#include <stdio.h>  
#include <stdlib.h> 
 
//Functions on stack
void push();  
void pop();  
void display(); 

//Stack using Linked list 
struct node   
{  
int data;  
struct node *next;  
};  
struct node *head;  
  
void push () //pushing elements 
{  
    int value;  
    struct node *ptr = (struct node*)malloc(sizeof(struct node));  
     //The last node in the linked list points to NULL 
    if(ptr == NULL)  
    {  
        printf("\nThe stack is already full, can't push more");   
    }  
    else   
    {  
        printf("\n\nEnter a value to push:");  
        scanf("%d", &value);
        //If the Stack is empty  
        if(head == NULL)  
        {         
            ptr -> data = value;  
            ptr -> next = NULL;  
            head = ptr;  
        }   
        else   
        {  
            ptr -> data = value;  
            ptr -> next = head;  
            head = ptr;  
               
        }  
        printf("%d pushed", value);  
    }
    printf("\nResultant stack:");
    display();
}  
  
void pop() //popping element from the stack
{  
    int item;  
    struct node *ptr;  
    if (head == NULL) //empty stack 
    {  
        printf("\nThe stack is empty, can't pop");  
    }  
    else  
    {  
        item = head -> data;  
        ptr = head;  
        head = head -> next;  
        free(ptr);     
    }
    printf("\nResultant stack:");
    display(); 
}  
void display()  
{  
    int i;  
    struct node *ptr;  
    ptr = head;  
    if(ptr == NULL)  
    {  
        printf("\nEmpty stack");  
    }  
    else  
    {  
        printf("\nThe stack: ");  
        while(ptr != NULL)  
        {  
            printf("%d ",ptr -> data);  
            ptr = ptr -> next;  
        }  
    }  
}  
void main()  
{  
    printf("Push operation: ");
    push();
    push();
    push();
    printf("\n\nPop operation: ");
    pop();
}  

输出

Push operation:

Enter a value to push:100
100 pushed
Resultant Stack:
The Stack: 100

Enter a value to push:200
200 pushed
Resultant Stack:
The Stack: 200 100

Enter a value to push:300
300 pushed
Resultant Stack:
The Stack: 300 200 100

Pop operation:
Resultant Stack:
The Stack: 200 100
--------------------------------
Process exited after 5.783 seconds with return value 0
Press any key to continue . . .

我们编写了两个方法**push和pop**来实现栈。我们需要确保两点：

执行push时，我们应该始终将元素添加到链表的开头。——**LI（先入）**
执行pop时，必须删除第一个元素。——**FO（先出）**
我们创建了**isEmpty()**和**peek()**来检查栈是否为空，因为如果栈为空，我们就无法执行pop。

队列

队列是一种线性数据结构，与栈类似，但队列的实现原理是**FIFO（先进先出）**。这意味着插入队列的元素将是第一个从队列中出来的元素，而在栈中，最后压入的元素将是第一个被弹出的。

关于队列的重要注意事项

队列将有两个末端——前端和后端。
元素从前端插入，从后端删除。

队列在现实生活中的例子

**队列：**在我们日常生活中，我们经常看到人们在各种地方排队，如电影院、KFC令牌柜台等。开始排队的人将是第一个拿到票的人。
**单行道：**首先进入车道的汽车将是第一个先出车道的。

术语

向队列插入元素：**enqueue**
从队列中删除元素：**dequeue**
开头的元素：**front**
末尾的元素：**rear**

我们可以在C语言中实现队列

使用数组
使用链表
使用栈

1. 使用数组

#include<stdio.h>   
#include<stdlib.h>   
#define maxsize 10
 
//Functions on queue
void enqueue();  
void dequeue();  
void display();  
int front = -1, rear = -1;
int queue[maxsize];  

//Inserting elements-enqueue
void enqueue()  
{  
    int item;  
    printf("\n\nEnter an element to insert into the queue: ");  
    scanf("%d", &item);  
    //If the queue is filled    
    if(rear == maxsize - 1)  
    {  
        printf("\nThe queue is already full, can't insert more elements");  
        return;  
    }
    //Empty queue
    else if(front == -1 && rear == -1)  
    {  
        front = 0;  
        rear = 0;  
    }  
    else   
    {  
        rear = rear + 1;  
    }  
    queue[rear] = item;  //inserting the element
    printf("%d inserted", item);
    printf("\nThe resultant queue:");
    display();      
}  

//Deleting elements from queue-dequeue
void dequeue()  
{  
    int item;   
    if (front == -1 || front > rear)  //empty queue
    {  
        printf("\nQueue is empty, can't delete elements");  
        return;  
    }  
    else  
    {  
        item = queue[front];  
        if(front == rear)  
        {  
            front = -1;  
            rear = -1 ;  
        }  
        else   
        {  
            front = front + 1;  
        }    
    }  
	printf("\nThe resultant queue:");
	display();   
}  
      
void display()  
{  
    int i;  
    if(rear == -1)  
    {  
        printf("\nEmpty queue");  
    }  
    else  
    {    
        for(i = front; i <= rear; i++)  
        {  
            printf("%d ",queue[i]);  
        }     
    }  
}  

void main ()  
{  
    printf("Enqueue operation:");
    enqueue();
    enqueue();
    enqueue();
    printf("\n\nDequeue operation:");
    dequeue();
}  

输出

Enqueue operation:

Enter an element to insert into the queue: 100
100 inserted
The resultant queue:100

Enter an element to insert into the queue: 200
200 inserted
The resultant queue:100 200

Enter an element to insert into the queue: 300
300 inserted
The resultant queue:100 200 300

Dequeue operation:
The resultant queue: 200 300
--------------------------------
Process exited after 5.774 seconds with return value 2
Press any key to continue . . .

请注意，队列有两个端点，“front”和“rear”。初始时初始化为-1，队列为空。
对于每次enqueue操作，我们都会向队列添加一个索引。
元素从后端插入，从前端删除。
对于每个 enqueue(): rear = rear + 1
对于每个 dequeue(): front = front + 1

**rear：（插入顺序）：** H - E - L - L - O(0 -> 1 -> 2 -> 3 -> 4)

**front：（删除顺序）：** O - L - L - E - H(4 -> 3 -> 2 -> 1 -> 0)

2. 使用链表

#include<stdio.h>   
#include<stdlib.h> 

//Linked list 
struct node   
{  
    int data;   
    struct node *next;  
};  

//Functions and ends in queue
struct node *front;  
struct node *rear;   
void enqueue();  
void dequeue();  
void display();  

void enqueue()  
{  
    struct node *ptr;  
    int item;   
    ptr = (struct node *)malloc(sizeof(struct node));  
    if(ptr == NULL)  //last node in Linked list points to NULL
    {  
        printf("\nQueue is already full, can't insert element");  
        return;  
    }  
    else  
    {   
        printf("\n\nEnter the value to insert: ");  
        scanf("%d", &item);  
        ptr -> data = item;  
        if(front == NULL)  
        {  
            front = ptr;  
            rear = ptr;   
            front -> next = NULL;  
            rear -> next = NULL;  
        }  
        else   
        {  
            rear -> next = ptr;  
            rear = ptr;  
            rear -> next = NULL;  
        }  
    } 
    printf("Resultant queue: ");
    display();
}
     
void dequeue()  
{  
    struct node *ptr;  
    if(front == NULL)  //Empty queue
    {  
        printf("\nThe queue is empty, can't delete from it");  
        return;  
    }  
    else   
    {  
        ptr = front;  
        front = front -> next;  
        free(ptr);  
    }  
    printf("Resultant queue: ");
    display();
} 
 
void display()  
{  
    struct node *ptr;  
    ptr = front;      
    if(front == NULL)  
    {  
        printf("\nEmpty queue");  
    }  
    else  
    {     
        while(ptr != NULL)   
        {  
            printf("%d ",ptr -> data);  
            ptr = ptr -> next;  
        }  
    }  
}  

void main ()  
{  
   printf("Enqueue operation: ");
   enqueue();
   enqueue();
   enqueue();
   printf("\n\nDequeue operation: ");
   dequeue();
   
}  

输出

Enqueue operation:

Enter the value to insert: 100
Resultant queue: 100

Enter the value to insert: 200
Resultant queue: 100 200

Enter the value to insert: 300
Resultant queue: 100 200 300

Dequeue operation: Resultant queue: 200 300
--------------------------------
Process exited after 4.771 seconds with return value 0
Press any key to continue . . .

使用数组的实现不能用于大规模应用。因此，链表用于实现队列。
front和rear是两个指向队列末端的指针。如果front和rear都为NULL，则队列为空。
每次插入时，rear指向下一个索引（NULL），每次删除时，front指向下一个索引。
插入元素到队列时，每个元素都从链表的末尾插入——**FI（先入）**
元素从链表的开头删除。——**FO（先出）**

3. 使用栈

栈遵循LIFO原则，而队列遵循FIFO。那么，它是如何工作的呢？

让我们举个例子

有一个栈，我们将元素压入其中

现在，如果我们执行pop操作，将弹出300。但是，根据队列的原则，应该删除100。

我们需要再创建一个栈，比如stack2，然后将我们的栈中的元素弹出到stack2中。

现在，我们可以从stack2中弹出元素。这将等同于队列中的enqueue操作。

我们可以用两种方式使用栈来实现队列

1. 使dequeue操作变得昂贵

在上面的例子中，当我们向第一个栈插入元素时，它不会改变——O(1)。但是，当我们执行dequeue时，我们首先需要将元素弹出到另一个栈，然后从那个栈中——dequeue操作变得昂贵——O(n)。

2. 使enqueue操作变得昂贵

我们来看一个例子

我们有一个栈“stack1”，其中有一个元素——100

当我们需要在栈上执行enqueue时，stack1中所有现有的元素都被弹出到stack2。
假设200被插入到stack1。现在，所有被弹出到stack2的元素又被推回stack1。
这样，通过stack2，第一个进入的元素始终保留在stack1的顶部。

这是一个使用第一种方式实现的程序——**使dequeue操作变得昂贵：**

#include<stdio.h>  
#define N 5  

int stack1[5], stack2[5];     
int top1 = -1, top2 = -1;   
int count=0;  
 
//O(1)-normal enqueue operation
void push1(int data)  //pushing the element into the first Stack
{  
 	if(top1 == N-1)  
	{  
   		printf("\nQueue is full, can't insert elements");  
	}	  
	else  
	{	  
   		top1++;   
   		stack1[top1]=data;   
	}  
}  
//Popping elements from stack1
int pop1()  
{     
	if(top1 == -1)  
	{    
	}  
	else  
	{  
   		int temp = stack1[top1];  
   		top1--;   
   		return temp;   
	}  
}   
  //Pushing the popped elements from stack1 to stack2
void push2(int x)  
{    
	if(top2 == N-1)  
	{	    
	}  
	else  
	{  
   		top2++;   
    	stack2[top2] = x;     
	}  
}   
  //Dequeue operation-O(n)
int pop2()  
{  
	int element = stack2[top2];   
   	top2--;   
   	return element;  
}
   
//Queue operations
void enqueue(int element)  
{  
    push1(element); 
    count++;  
}
void dequeue()  
{  
	int i;
   	if((top1 == -1) && (top2 == -1))  
	{	  
   		printf("\nEmpty queue, can't pop");  
	}  
	else  
	{  
		int i;
  		for(i = 0; i < count; i++)  
  		{	  
     			int element = pop1();  
     			push2(element);  
  		}  
		int b = pop2();  
		printf("\nThe deleted element is %d", b);  
		printf("\n");  
		count--;  
		for(i = 0; i < count; i++)  
		{  
   			int a = pop2();  
   			push1(a);   
		}  
	}
} 
 //Displays the elements of the second Stack
void display()  
{  
	int i;
	for(i = 0; i <= top1; i++)  
  	{  
     	printf("%d ", stack1[i]);  
  	}  
}  
void main()  
{  
   enqueue(10); 
   enqueue(20);  
   enqueue(30);
   printf("Enqueue operation-after inserting 10, 20 and 30:");
   display();
   printf("\n\nDequeue operation:");
   dequeue();
   printf("Resultant queue:");  
   display();   
}  

输出

Enqueue operation-after inserting 10, 20 and 30:10 20 30

Dequeue operation:
The deleted element is 10
Resultant queue:20 30
--------------------------------
Process exited after 0.8232 seconds with return value 1
Press any key to continue . . .

程序中的函数

push1()	给定一个元素，它会将该元素压入stack1
pop1()	将stack1的最后一个元素存储在temp中并返回。
push2()	将元素压入stack2
pop2()	从stack2中弹出元素
enqueue()	调用push1
dequeue()	调用push2，传入pop1()返回的temp，然后调用pop2()

下一主题C语言中的员工记录系统

C语言数据结构与算法 | 第二集

栈和队列

栈

栈的函数

Push和Pop

现实生活中的栈的例子

栈的实现

队列

关于队列的重要注意事项

程序中的函数

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C语言数据结构与算法 | 第二集

栈和队列

栈

栈的函数

Push和Pop

现实生活中的栈的例子

栈的实现

队列

关于队列的重要注意事项

程序中的函数

相关帖子

C 语言 FCFS 程序

C 语言结构体指针

C 语言 ctype.h

C 语言从数组中删除重复元素

Bootstrap 中的响应式图像与示例

C 语言线性搜索程序

C 语言多维数组

C 语言孪生素数

C 语言 Fread() 函数

C 语言 float 和 double 的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器