数据结构 - 栈 - 队列

数据结构>栈和队列

栈, 队列

Posted by LYF on March 20, 2025

介绍

image-20250331220238254

栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一 端称为队头。

声明

//栈
//静态定长栈
#define N 10
typedef int STDataType;

typedef struct Stack
{
 	STDataType _a[N];
 	int _t
}Stack;
//动态增长栈
typedef struct Stack
{
	STDataType* _a;
 	int _top;      // 栈顶
	int _capacity;  // 容量 
}Stack;

//链式队列
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode *head; //front
	QueueNode *tail; //rear
}Queue;

栈基本操作实现


typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//容量
}Stack;


void StackInit(Stack* st)
{
	assert(st);
	st->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	st->top = 0;
	st->capacity = 4;
}

void StackDestory(Stack* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->top = 0;
	st->capacity = 0;
}

void StackPush(Stack* st, STDataType x)
{
	assert(st);
	//栈容量不足进行扩容
	if (st->top >= st->capacity)
	{
		st->capacity *= 2;
		//把原数组拷贝到tmp中
		STDataType* tmp = (STDataType*)realloc
		(st->a, sizeof(STDataType) * st->capacity);
		if (tmp==NULL)
		{
			printf("内存不足");
			exit(-1);
		}
		else
		{
			st->a = tmp;
		}
		
	}
	//st->top指向当前要插入的位置
	st->a[st->top] = x;
	st->top++;
}

void StackPop(Stack* st)
{
	assert(st);
	assert(st->top > 0);
	st->top--;
}
//获取栈顶元素
STDataType StackTop(Stack* st)
{
	assert(st);
	assert(st->top > 0);
	
	return st->a[st->top-1];
	
		 
}
//栈中元素个数
int StackSize(Stack* st)
{
	assert(st);
	return st->top;
}
//栈是否为空
int StackEmpty(Stack* st)
{
	assert(st);
	return st->top == 0 ? 1 : 0;
	
}

队列基本操作

//单链表实现队列
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;


//队列初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
//队列销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* node = cur;
		cur = cur->next;
		free(node);
		
	}
	pq->head = pq->tail = NULL;
	

}
//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建新结点
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		printf("内存不足\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	//队列是否为空
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
	
}
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}
//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->data;
}
//判断队列是否为空
int QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL ? 1 : 0;
}
//获取队列中有效元素的个数
int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

OJ

1.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

算法思路：利用栈的后进先出特性，进行括号的匹配，当遍历到左括号就进行入栈，遍历到右括号就让其与栈顶元素进行比较，满足就让栈顶元素出栈，继续向下遍历字符，如果其与栈顶元素不相等直接返回false，注意：跳出循环有两种情况，一种时字符遍历完，另一种时匹配失败。

bool isValid(char* s) {

    Stack st;
    StackInit(&st);
    bool ret;

    while(*s)
    {
        
        if(*s == '('||*s == '{'||*s == '[')
        {
            StackPush(&st,*s);
        }
        else
        {   //如果栈内已经空
            if(StackEmpty(&st))   
            {
                ret=false;
                break;
                //return false;
            }    
                
            //获取栈顶元素
            char top = StackTop(&st);
            if(*s == ')' && top != '(')
            {
                ret=false;
                break;
                //return false;
            }  
            if(*s == '}' && top != '{')
            {
                ret=false;
                break;
                //return false;
            }  
            if(*s == ']' && top != '[')
            {
                ret=false;
                break;
                //return false;
            }  
            
            StackPop(&st);    
            
        }

        
        s++;
    }
    //字符串遍历完
    if(*s=='\0')
    {
        ret = StackEmpty(&st);
    }

    StackDestory(&st);
    return ret;
    
}

2.用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

3.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

3.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

4.设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

算法思路：

typedef struct {
    int *_a;
    int _front;//指向对头
    int _rear;//指向队尾
    int _k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //开k+1个空间大小,循环队列要留一个位置
    q->_a = (int*)malloc(sizeof(int)*(k+1));
    q->_front = 0;
    q->_rear = 0;

    //后边取模要用
    q->_k = k;

    return q;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    
    return obj->_front==obj->_rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    
    return (obj->_rear+1)%(obj->_k+1) == obj->_front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        
        obj->_a[obj->_rear] = value;
        obj->_rear++;
        obj->_rear %= (obj->_k+1);
        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->_front++;
        obj->_front %= (obj->_k+1);
        return true;
    }
    
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->_a[obj->_front];
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        //rear指向要插入元素的位置
        int tail = obj->_rear-1; 
        if(tail == -1)
            tail = obj->_k;//注意：数组下标是 0 ~ k
        return obj->_a[tail];
    }
    
}



void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->_a);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/
CATALOG
    FEATURED TAGS
    iOS 开发技巧 Debug Obj-C Xcode ReactiveCocoa 函数式编程 开源框架 Runtime 生活 Blog Mac 效率 终端 Git Swift CocoaPods zsh 开源库 ruby shell 健身
    FRIENDS