数据结构-栈，队列

2024-03-22 21:44:46

0PTA截图

数据结构-栈，队列

1本周学习总结

1.1栈

数据结构-栈，队列
栈式一种只能在一端进行插入或删除操作的线性表，表中允许插入、删除操作的一端为栈顶。
栈中元素特性：具有线性关系，后进先出
进出栈规则：栈顶出栈，栈底最后出栈；时进时出，元素未完全进栈时，即可出栈。

  • 顺序栈
    顺序栈四要素
    1、栈空：top=-1
    2、栈满：top=MaxSize-1
    3、进栈e操作：top++;st->data[top]=e
    4、退栈操作：e=st->data[top];top--
    操作函数
    结构体
typedef struct
{
    ElemType data[MaxSize];
    int top;//栈顶指针
}Stack;
typedef Stack *SqStack;

1、初始化

void InitStack(&s)
{
    s=new Stack;
    s->top=-1;
}

2、销毁栈

void DestroyStack(SqStack &s)
{
    delete s;
}

3、判断栈空

bool StackEmpty(s)
{
    return(s->top==-1)
}

4、创建栈

Stack CreateStack(int MaxSize)
{
    Stack s=(Stack)malloc(sizeof(struct SNode));
    s->Data=(ElementType *)malloc (MaxSize*sizeof(ElementType));
    s->top=0;
    s->MaxSize = MaxSize;
    return s;
}

5、进栈

bool Push (SqStack &s,ElemtType e)
{
    if(s->top==MaxSize-1)//顺序栈务必考虑栈满
    return false;
    s->top++;//顶指针增1
    s->Data[s->top]=e;
    return true;
}

6、出栈

bool Pop(SqStack &s,ElemType &e)
{
    if(s->top==-1)//栈为空，栈下益出
    return false';
    e=s->Data[s->top];//取栈顶指针元素
    s->top--;
    return true;
}

链栈

数据结构-栈，队列

采用链表存储结构称为链栈

  • 链栈的结构体
typedef int ElemType;
typedef struct Linknode
{
    ElemType data;//数据域
    struct Linknode *next;//指针域
}LinkNode, *LiStack;
  • 栈的四要素
    1、栈空：s->next==NULL;
    2、栈满：不考虑
    3、进栈e操作：节点插入到头节点后，链表头插法
    4、退栈操作：取出头节点之后节点的元素并删除
  • 栈的基本运算
    1、初始化栈
void InitStack(LiStack &s)
{
    s=new LiNode;
    s->next=NULL;
}

2、销毁栈

void DestroyStack(LiStack &s)
{
    LiStack node;
    whilw(s!=NULL)
    {
      node=s;
      s=s->next;
      delete node;
     }
}

3、判断栈是否为空

bool StackEmpty(LiStack &s)
{
    return (s->next==NULL);
}

4、进栈

void Push (LiStack &s)
{
    LiStack p;
    p=new LiNode;
    p->data=e;
    p->next=s->next;
    s->next=p;
}

5、出栈

bool pop(LiStack &s,ElemType &e)
{
    LiStack p;
    if(s->next==NULL)
    return false;
    p=s->next;
    e=p->data;
    s->next=p->next;
    delete p;
    return true;
}

6、取栈顶元素

bool GetTop(LiStack s,ElemType &e)
{
    if(s->next==NULL)
    return false;
    e=s->next->data;
    return true;
}

1.2栈的应用

  • 表达式
    数据结构-栈，队列
    本题的测试点有一个比较难想到：第一个数为正数，且带有正号，则不输出；中间的数为正数也带有正号，但输出不带正号
#include <iostream>
#include<stack>
using namespace std;
stack<char>s;
char str[1000];
int main()
{
	int i = 0,flag=0;
	cin >> str;
	for (; str[i] != '\0'; i++)
	{
		if ((i == 0 && (str[i] == '-'||str[i]=='+')) || (i>=1&&str[i - 1] == '(' &&( str[i] == '-'||str[i]=='+')))//判断负号
		{
            if(str[i]=='+'&&i==0){
                flag = 0;
            }
            else if(str[i]=='+'){
                cout<<" ";flag=0;
            }
			else if (flag == 0)cout << str[i];
			else cout << " " << str[i];
			flag = 0;
		}
		else if (str[i] == '+' || str[i] == '-') {//+或-
			while (!(s.empty()||s.top() == '('))
			{
				cout << " " << s.top();
				s.pop();
			}
			s.push(str[i]);
		}
		else if (str[i] == '*' || str[i] == '/')
		{
			while (!s.empty() && (s.top() == '/' || s.top() == '*'))
			{
				cout << " " << s.top();
				s.pop();
			}
			s.push(str[i]);
		}
		else if (str[i] == '(')s.push(str[i]);
		else if (str[i] == ')') {
			while (s.top() != '(')
			{
				cout << " " << s.top();
				s.pop();
			}
			s.pop();
		}
		//  3*(-4)
		else if ((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
		{
			if (flag)cout << " ";
			while ((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
			{
				 cout << str[i];
				i++;
			}
			i--;
			flag = 1;
		}
		
	}

	while (!s.empty())
	{
		cout << " " << s.top();
		s.pop();
	}

	return 0;
}

1.3队列

数据结构-栈，队列

只允许在表的一段进行插入，而在表的另一端进行删除的线性表。
队尾(rear)--允许插入的一端
队头（front)--允许删除的一端
队列特点：先进先出
应用：操作系统，销售系统，打印机，手机短信发送

  • 顺序队
    顺序队四要素（初始时 front=rear=-1)
    1、队空：front=rear;
    2。队满：rear=MaxSize-1;
    3、元素e进队：raer++;data[rear]=e;
    4、元素e出队：front++;e=data[front];
    结构体 
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;//队首和队尾指针    
}Queue;
typedef Queue *SqQueue;

1、初始化

void InitQueue(SqQueue &q)
{
    q=new Queue;
    q->front=q->rear=-1;
}

2、销毁队列

void DestroyQueue(SqQueue &q)
{
    delete q;
}

3、判断队列是否为空

bool QueueEmpty(SqQueue q)
{    
    return (q->front==q->rear);
}

4、进队列

bool enQueue(SqQueue &q,ElemType e)
{
    if(q->rear+1==MaxSize)
    return false;
    q->rear=q->rear+1;
    q->data[q->rear]=e;
    return true;
}

5、出队列

bool deQueue(SqQueue &q,ElemType &e)
{
    if(q->front==q->rear)
    return false;
    q->front=q->front+1;
    e=q->data[q->front];
    return true;
}
  • 环形队列
    数据结构-栈，队列

把存储队列元素的表从逻辑上看成一个环。

  • 操作函数
    1、初始化
void InitQueue(SqQueue &q)
{
    q=new Queue;
    q->front=q->rear=0;
}

2、队满:(rear+1)%MaxSize=front;
3、队空：front=rear;
4、入队

bool enQueue(SqQueue &q,ElemType e)
{
    if((q->rear+1)%MaxSize==0)
    return false;
    q->rear=(q->rear+1)%MaxSize;
    q->data[q->rear]=e;
    return true;
}

5、出队

bool deQueue(SqQueue &q,ElemType &e)
{
    if(q->front==q->rear)
    return false;
    q->front=(q->front+1)%MaxSize;
    e=q->data[q->front];
    return true;
}
  • 队列应用
    舞伴问题
    数据结构-栈，队列
    本题应该使用循环队列，否则或答案错误
int QueueLen(SqQueue Q)//队列长度 
{
    return (Q->rear - Q->front);
}
int EnQueue(SqQueue& Q, Person e)//加入队列
{
    if (Q->rear == MAXQSIZE - 1)
        return false;
    Q->data[(++Q->rear)%MAXQSIZE] = e;
    return true;
}
int QueueEmpty(SqQueue& Q)//队列是否为空 
{
    if (Q->front == Q->rear)
        return 1;
    return 0;
}
int DeQueue(SqQueue& Q, Person& e)//出队列
{
    if (Q->front == Q->rear)
        return false;
    (++Q->front)%MAXQSIZE;
    e = Q->data[Q->front];
    return true;
}
void DancePartner(Person dancer[], int num) //配对舞伴 
{
    Person p;
    int i;
    for (i = 0; i < num; i++)
    {
        p = dancer[i];
        if (p.sex == 'M')
        {
            EnQueue(Mdancers, p);

        }
        else
            EnQueue(Fdancers, p);
    }
    while (!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers))
    {
        DeQueue(Fdancers, p);
        cout << p.name << "  ";
        DeQueue(Mdancers, p);
        cout << p.name <<endl;
    }
    return ;
}

2PTA实验作业

2.1符号配对

**思路及伪代码
定义一个字符类型的栈；和字符串型的leftchar,rightchar分别存放左右括号；令flag=0；当输入的字符不为空时，利用 stack库里的find函数，若左右括号都存在，flag=1;如果栈空且有右括号存在，return false;如果配对成功，出栈；否则进栈；如果flag=1且栈空，return true;否则如果flag=1,输出栈顶元素，return false;否则 return true;

	stack <char> st;
	string leftchar = "([{";
	string rightchar = ")]}";
	int i;
	int flag = 0;
	char str = bracket_str[i++];
	while(str)
		if leftchar.find(str) != -1 || rightchar.find(str) != -1//左括号和右括号都存在
		then
			flag = 1;
			if st.empty() && rightchar.find(str) != -1//栈空，有右括号
                            then
				return false;
			else if !st.empty() && rightchar.find(str) != -1&&rightchar.find(str)==leftchar.find(st.top())//配对成功
                              then
				st.pop();
                                end if
			else
				st.push(str);
		end if
		str = bracket_str[i++];
	end if
	if flag && st.empty()
            then 
		return true;
             end if
	else if flag
	   then
		cout << st.top()<<"\n";
		return false;
	    end else if 
	else
		return true;

用到了stack库里的find（找） empty（判断空） push（进栈） pop（出栈） top(取栈顶元素）函数，使代码更加简洁，提高了效率，利用了栈这一结构存放符号

2.2银行排队

  • 思路
    利用for循环，将用户的编号输入，并利用%判断奇数或偶数，奇数排到A对队列，偶数排到B队列。解决输出问题，若A不为空则直接输出，否则输出B。利用while循环，当两个中有不为空的时候输出前面带有空格的数据。
	int num;//顾客人数
	int i;
	int temp;//顾客编号
	cin >> num;
	queue<int>A, B;
	for  i = 0 to num-1
	
		cin >> temp;
		if (temp % 2)//偶数
                    then
			A.push(temp)
                    end if
		else
			B.push(temp)
	
	int flag = 0;
	if !A.empty()
	
	      then	
		cout << A.front();
		A.pop();
		i = 1;
	      end if
	else
			cout << B.front();
		B.pop();
	end else
	while !A.empty() || !B.empty()
	
		i++;
		if i % 2
		then
			if !A.empty()
			then
				cout <<" "<< A.front();
				A.pop();
			end if
		end if
		else
		
			if !A.empty())
			then
				cout << A.front();
				A.pop();
			end if
			if !B.empty()
			then
				cout <<" "<< B.front();
				B.pop();
			end if
		
	end while

3阅读代码

数据结构-栈，队列

  • 思路：
    从队列尾部插入元素时，我们可以提前取出队列中所有比这个元素小的元素，使得队列中只保留对结果有影响的数字。这样的方法等价于要求维持队列单调递减，即要保证每个元素的前面都没有比它小的元素。

  • 代码
    数据结构-栈，队列

  • 时间复杂度
    O(1)（插入，删除，求最大值）
    删除操作于求最大值操作显然只需要 O(1) 的时间。
    而插入操作虽然看起来有循环，做一个插入操作时最多可能会有 n 次出队操作。但要注意，由于每个数字只会出队一次，因此对于所有的 n 个数字的插入过程，对应的所有出队操作也不会大于 n次。因此将出队的时间均摊到每个插入操作上，时间复杂度为 O(1)。

  • 空间复杂度
    O(n)，需要用队列存储所有插入的元素

  • 难点
    如何高效实现一个始终递减的队列？
    只需要在插入每一个元素 value 时，从队列尾部依次取出比当前元素 value 小的元素，直到遇到一个比当前元素大的元素 value' 即可。

  • 优势
    从队列尾部取出元素，因此需要使用双端队列来实现。另外我们也需要一个辅助队列来记录所有被插入的值，以确定 pop_front 函数的返回值。

保证了队列单调递减后，求最大值时只需要直接取双端队列中的第一项即可。

上一篇：PTA 浙大版《数据结构（第2版）》题目集 习题3.5 求链表的倒数第m个元素 (20 分)


下一篇：数据结构